Day 13 : 一維搜尋法(line search)

第 11 屆 iThome 鐵人賽

DAY 13

AI & Data

連接數學與現實世界的橋樑 -- 數學建模系列第 13 篇

11th鐵人賽一維搜尋法等區間搜尋法黃金分割法

spidyjames

2019-09-14 21:34:35

1124 瀏覽

分享至

在求解非線性規劃問題時，我們利用迭代的方式來求解， $\bar X^{(k+1)} = \bar X^{(k)} + \alpha_k \bar d^{(k)}$ ，決定方向與步長就變得重要了。方向為朝函數極值的方向，而步長則可透過解析法與數值法求得。今天要來繼續討論昨天提到的Interval reducing method。

等區間搜尋法(Equal interval search)

給定初始值， $a_0$ , $\delta$ , $\epsilon$
比較相鄰之點的函數值大小，直到 $f(a_n) < f(a_{n+1})$
則 $\alpha_l = a_{n-1}, \alpha_u = a_{n+1}$ ，又 $a_n = a_0 + n\delta, n = 0, 1, \dots$
$\Rightarrow I = \alpha_u - \alpha_l = 2\delta$
縮小區間 $I$ ，ex:令 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cdelta'%20%3D%20%5Cfrac%7B%5Cdelta%7D%7B10%7D$ ，再由 $\alpha_l$ 開始，重複步驟2，直到 $I < \epsilon$ $https://chart.googleapis.com/chart?cht=tx&chl=%5CRightarrow%20%5Calpha%5E%7B%5Cast%7D%20%3D%20%5Cfrac%7B%5Calpha_l%20%2B%20%5Calpha_u%7D%7B2%7D$

黃金分割法(Golden section search)

可視為一種可變區間的搜尋法，此法分兩階段，

找出單峰函數的區間黃金比( $golden ratio = 1.618$ )
區間分割方式:
$q = 0$ , $\alpha_0 = \delta + (1.618)^{0} \delta$
$q = 1$ , $\alpha_1 = \alpha_0 + (1.618)^{1} \delta$
$q = 2$ , $\alpha_2 = \alpha_1 + (1.618)^{2} \delta$
$\dots$
$\Rightarrow \alpha_q = \sum_{j=0}^{q} \delta (1.618)^{j}$ , $q=0,1,2, \dots$
比較相鄰2點函數值，直到 $f(\alpha_{q-1}) < f(\alpha_{q-2})$ 且 $f(\alpha_{q-1}) < f(\alpha_q)$
$\Rightarrow$ 令 $\alpha_u = \alpha_q$ , $\alpha_l = \alpha_{q-2}$
起始不確定區間為， $I = \alpha_u - \alpha_l = \alpha_q - \alpha_{q-2}$
縮減區間
舉例說明，